//apologies that this code is not more robust!
import java.util.*;
public class Unit6
{
	//shortest route calculations... does it for whole graph
	public static void calculateShortestRoutes(City city){
		//prior to this, all current distances should be 0 and previouses should be null
		//set current distance for home port
		city.setCurrentDistance(0.0);
		//make a list of cities
		ArrayList cityList = new ArrayList();
		//add the starting city to list
		cityList.add(city);
		//while we still have cities to process
		while (!cityList.isEmpty()) {
			//look for the least far away city
			City leastCity = null;
			//loop through cities
			for(Object o : cityList){
				//cast city from object
				City theCity = (City)o;
				//if there is no least city....
				if(leastCity==null){
					//...thats the one...
					leastCity = theCity;
				//...otherwise if we find a closer city...
				}else if(theCity.getCurrentDistance()<leastCity.getCurrentDistance()){
					//...then /that/ is the one
					leastCity = theCity;
				}
			}
			//found the least city!
			//remove it from list, to avoid infinite loop
			cityList.remove(leastCity);
			//enumerate routes
			for(Object o: leastCity.getRoutes()){
				//cast route from object
				Route theRoute = (Route)o;
				//grab city from route
				City theCity = theRoute.getCity();
				//pull out distance
				double theDistance = theRoute.getDistance();
				//calculate total distance
				double totalDistance = leastCity.getCurrentDistance() + theDistance;
				//if this total distance is better...
				if(totalDistance<theCity.getCurrentDistance()){
					//remove the destination city from the list(or nothing if it isnt there)
					cityList.remove(theCity);
					//set the new total distance
					theCity.setCurrentDistance(totalDistance);
					//set the least city as the previous
					theCity.setPrevious(leastCity);
					//put it back on the list
					cityList.add(theCity);
				}
			}
		}
	}
	//list cities with numbers next to them (used a lot in the UI)
	public static void listCities(ArrayList theCityList){
		//loop through cities
		for(int index=0;index<theCityList.size();++index){
			//print number and city
			System.out.println(index+" - "+((City)theCityList.get(index)).getName());
		}
	}
	//main function
	public static void main( String [] args){
		//create a scanner
		Scanner theScanner = new Scanner(System.in);
		//a reusable "done" flag
		boolean done = false;
		//list of cities
		ArrayList cityList = new ArrayList();
		//phase 1 - enter city names
		System.out.println("Add Cities (enter a blank line when finished):");
		//until we are done...
		while(!done){
			//prompt for city name
			System.out.print("City name: ");
			//read a line
			String input = theScanner.nextLine();
			//if nothing entered, we are done, otherwise add city to list
			if(input.length()==0){
				done = true;
			}else{
				cityList.add(new City(input));
			}
		}
		//phase 2 - adding routes
		done = false;
		System.out.println("Add Routes:");
		//while not done...
		while(!done){
			//grab a first city
			listCities(cityList);
			System.out.print("First City(-1 means done): ");
			int first = theScanner.nextInt();
			theScanner.nextLine();
			//input check for -1, meaning we're done with routes
			if(first==-1){
			 	done=true;
			}else{
				//input second city
				listCities(cityList);
				System.out.print("Second City: ");
				int second = theScanner.nextInt();
				theScanner.nextLine();
				//input distance
				System.out.print("Distance: ");
				double distance = theScanner.nextDouble();
				theScanner.nextLine();
				//grab cities from list
				City firstCity = (City)cityList.get(first);
				City secondCity = (City)cityList.get(second);		
				//add two routes, one from a to b, and one from b to a
				firstCity.getRoutes().add(new Route(secondCity,distance));
				secondCity.getRoutes().add(new Route(firstCity,distance));
			}
		}
		//phase 3 - look at distances
		done = false;
		while(!done){
			//choose a city of origin
			System.out.println("Find routes for (-1 when finished):");
			listCities(cityList);
			int start = theScanner.nextInt();
			theScanner.nextLine();
			//check for exit condition
			if(start==-1){
			 	done = true;
			}else{
				//initialize total distances
				for(Object o : cityList){
					City city = (City)o;
					city.setPrevious(null);
					city.setCurrentDistance(Double.POSITIVE_INFINITY);
				}
				//grab starting city
				City theCity = (City)cityList.get(start);
				//calculate routes from that city
				calculateShortestRoutes(theCity);
				//show distances and routes for all cities
				//loop through cities
				for(Object o: cityList){
					//grab out city
					City city = (City)o;
					//write name of city
					System.out.print(city.getName()+" - ");
					//check for infinite distance
					if(city.getCurrentDistance()==Double.POSITIVE_INFINITY){
						System.out.print("You can't get there from here!");
					}else{
						//non-infinite distance...
						//show distance
						System.out.print(city.getCurrentDistance()+" - ");
						//build route stack
						Stack cityStack = new Stack();
						//while we have not reached the origin, add to stack and move back
						while(city!=null){
							cityStack.push(city);
							city = city.getPrevious();
						}
						//write the route:
						//first flag hides an arrow the first go around
						boolean first = true;
						//while cities are in the stack...
						while(!cityStack.isEmpty()){
							//check first flag
							if(first){
								first = false;
							}else{
								System.out.print("->");
							}
							//grab city from stack
							city = (City)cityStack.pop();
							//write the city's name
							System.out.print(city.getName());
						}
					}
					//end the line
					System.out.println("");
				}
			}
		}
	}
}